class Solution {
    int tmp[50010];
public:
    int reversePairs(vector<int>& nums) {
        return MergeSort(nums,0,nums.size()-1);
    }
     int MergeSort(vector<int>& nums,int begin,int end)
    {
        if(begin>=end) return 0;
        int mid=(begin+end)/2;

        int ret=0;
        ret+=MergeSort(nums,begin,mid);
        ret+=MergeSort(nums,mid+1,end);

        //处理翻转对
        int begin1=begin,end1=mid;
        int begin2=mid+1,end2=end;

        while(begin1<=end1)
        {
            while(begin2<=end2&&nums[begin2]>=nums[begin1]/2.0)
            begin2++;

            if(begin2>end2)break;
            ret+=end-begin2+1;
            begin1++;
        }
        //处理一左一右
        begin1=begin,end1=mid;
        begin2=mid+1,end2=end;
        int j=0;
        while(begin1<=end1&&begin2<=end2)
        {
            if(nums[begin1]<=nums[begin2])
            {
                tmp[j++]=nums[begin2++];
            }
            else
            {
                tmp[j++]=nums[begin1++];
            }
        }
        while(begin1<=end1)  tmp[j++]=nums[begin1++];
        while(begin2<=end2)  tmp[j++]=nums[begin2++];

        for(int i=begin;i<=end;i++)
        nums[i]=tmp[i-begin];
        return ret;
    }
};
